--[[ -*- coding: utf-8 -*-

Sety - a lua library for creating and manipulating sets

version: 0.5
author: Lars Rosengreen
email: lrosengreen@gmail.com
website: http://www.googlecode.com/p/tabstools


The MIT License

Copyright (c) 2006, 2007, 2008 Lars Rosengreen (lrosengreen@gmail.com)

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE. 
]]


set={}
local mt = {}

-- create a set with table a as elements
-- usage: s = set{1, 2, 'apple'}
local function __call(_, a)
    local acc = {}
    for _, e in ipairs(a) do
        acc[e] = true
    end
    setmetatable(acc, mt)
    return acc
end
setmetatable(set, {__call=__call})


-- iterator for all set elements
-- useage: for e in elts(aset) do ...
local function elts(a)
    return pairs(a)
end
set.elts = elts

-- returns a shallow copy of a
local function copy(a)
    acc = set{}
    for e in elts(a) do
        acc[e] = true
    end
    return acc
end
set.copy = copy

-- if b is not a member of a then return false (would normally return nil)
local function index(a, b)
    return false
end
set.index = index


-- returns A ⊆ B
local function subset(a,b)
    local match = true
    for e in elts(a) do
        if (not b[e]) then
            match = false
            break
        end
    end
    return match
end
set.subset = subset


-- returns A = B
local function eq(a, b)
   return (a <= b) and (b <= a)
end
set.eq = eq


-- returns A ⊂ B
local function proper_subset(a, b)
    return (a <= b) and not (a == b)
end
set.proper_subset = proper_subset


-- returns A ⋃ B
-- mutating
local function m_union(a, b)
    for e in elts(b) do a[e] = true end
    return a
end
set.m_union = m_union
    

-- returns A ⋃ B
local function union(a, b)
    local acc = set{}
    for e in elts(a) do acc[e] = true end
    for e in elts(b) do acc[e] = true end
    return acc
end
set.union = union


-- returns A ⋂ B
-- mutating
local function m_intersection(a, b)
    for e in elts(a) do
        if not b[e] then
            a[e] = nil
        end
    end
    return a
end
set.m_intersection=m_intersection


-- returns A ⋂ B
local function intersection(a, b)
    return m_intersection(copy(a), b)
end
set.intersection = intersection


-- returns A - B
-- mutating
local function m_difference(a, b)
    for e in elts(b) do
        a[e] = nil
    end
    return a
end
set.m_difference = m_difference


-- returns A - B
local function difference(a, b)
    return m_difference(copy(a), b)
end
set.difference = difference


-- if b is a set then returns A ⋂ B, otherwise, returns A ⋂ set{b}
-- mutating
local function m_add(a, b)
    if getmetatable(b) == mt then
        return m_union(a, b)
    else
        a[b] = true
        return a
    end
end
set.m_add = m_add


-- if b is a set then returns A ⋂ B, otherwise, returns A ⋂ set{b}
local function add(a, b)
    return m_add(copy(a), b)
end
set.add = add


-- if b is a set then returns A - B, otherwise, returns A - set{b}
-- mutating
local function m_sub(a, b)
    if getmetatable(b) == mt then
        return m_difference(a, b)
    else
        a[b] = nil
        return a
    end
end
set.m_sub = m_sub


-- if b is a set then returns A - B, otherwise, returns A - set{b}
local function sub(a, b)
    return m_sub(copy(a), b)
end
set.sub = sub


-- returns the number of elements in a
local function cardinality(a)
    local count = 0
    for e in elts(a) do
        count = count + 1
    end
    return count
end
set.cardinality = cardinality


-- return a string with all of a's values concatenated together.  sep is an 
-- optional string inserted between consecutive elements.
local function concat(a, sep)
    if (not sep) then sep = '' end
    local acc = {}
        for e in elts(a) do
            acc[#acc + 1] = _G.tostring(e)
        end
    return table.concat(acc, sep)
end
set.concat = concat


-- returns a string representation of a
local function tostring(a)
    local acc = {}
    for e in elts(a) do
        if (type(e) == 'string') then
            acc[#acc + 1] = [[']] .. e .. [[']]
        else 
            acc[#acc + 1] = _G.tostring(e)
        end
    end
    return '{' .. table.concat(acc, ', ') .. '}'
end
set.tostring = tostring


-- useful for set.eq(A, set.empty), etc.
set.empty = set{}


-- A[e]: true if e ∈ A, otherwise false
-- A + B: add(a, b)
-- A - B: sub(a, b)
-- print(A): {'a', 'b', ...}
-- A == B: eq(a, b)
-- A ^ B: A ⋂ B
-- A <= B: A ⊆ B
-- A < B: A ⊂ B
mt = {__index=index, __add=add, __sub=sub, __tostring=tostring, __eq=eq, 
    __pow=intersection, __le=subset, __lt=proper_subset}
